/* 
 * File:   main.cpp
 * Author: Trunghpb
 *
 * Created on March 19, 2010, 9:09 AM
Tìm đỉnh trụ của đồ thị

INPUT
N là số đỉnh của đồ thị
các dòng tiếp là ma trận kề

OUTPUT
M dòng đầu là số đỉnh trụ
dòng tiếp theo là danh sách các đỉnh trụ
 */

#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100

#define TRUE 1
#define FALSE 0

int N, M;
int dtru[MAX], chuaxet[MAX], dke[MAX];
int a[MAX][MAX];
int sodinh;

// Đọc dữ liệu đầu vào
void input() {
    FILE *fi;
    fi = fopen("dothi.in", "r");
    fscanf(fi, "%d\n", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            fscanf(fi, "%d", &a[i][j]);
        }
    }
    fclose(fi);
}

void init_chuaxet() {
    for (int i = 0; i < N; i++) {
        chuaxet[i] = TRUE;
    }
}

int tim_duong(int t) {
    int queue[MAX];
    int dau = 0, cuoi = 0, u;
    queue[cuoi++] = t;  // đưa t vào hàng đợi
    chuaxet[t] = FALSE; // xem như t đã đi rồi
    do{
        u = queue[dau++];   // lần lượt lấy các đỉnh trong hàng đợi ra

        for(int v = 0; v<N; v++){
            if (a[u][v] && chuaxet[v]){ // với mọi đỉnh v chưa được đi và kề u
                chuaxet[v] = FALSE;     // đánh dấu v đã đi rồi.
                queue[cuoi++] = v;        // đưa v vào hàng đợi
            }
        }
    }while (dau < cuoi);    // thực hiện đến khi hàng đợi rỗng

    for(int i = 0; i<sodinh; i++){
        // những đỉnh kề với đỉnh được xem là tru có nằm trong danh sách đường đi không
        if (chuaxet[dke[i]]){
            return FALSE;   // nếu không có, nghĩa là không có đường đi tới tất cả các đỉnh kề trụ
        }
    }
    return TRUE;
}

void tim_tru() {
    int p = 0;
    for (int t = 0; t < N; t++) {
        init_chuaxet(); // Khởi tạo mảng chưa xét, tất cả các đỉnh là chưa đi
        sodinh = 0;     // số đỉnh kề của t
        for (int i = 0; i < N; i++) {
            if (a[t][i]) {  // với mọi đỉnh kề t
                p = i;      // chọn lấy một đỉnh bất kì phục vụ cho phép tìm đường
                dke[sodinh++] = i;  // lưu lại danh sách đỉnh kề để sử dụng sau này
                a[t][i] = 0;        // loại bỏ cạnh trực tiếp của i nối với t
                a[i][t] = 0;
            }
        }

        if (tim_duong(p) == FALSE) {    // nếu phép tìm được không có
            dtru[M] = t;    // thì t là đỉnh trụ
            M++;            // tăng số lượng đỉnh trụ
        }

        // phục hồi lại các đỉnh kề vừa bị loại bỏ
        for (int i = 0; i < sodinh; i++) {
            a[t][dke[i]] = 1;
            a[dke[i]][t] = 1;
        }
    }
}

void output() {
    FILE *fo;
    fo = fopen("dinhtru.out", "w");
    fprintf(fo, "%d\n", M);

    for (int i = 0; i < M; i++) {
        fprintf(fo, "%d ", dtru[i]+1);
    }

    fclose(fo);
}

/*
 * 
 */
int main(int argc, char** argv) {
    input();    // đọc dữ liệu đầu vào
    tim_tru();  // tìm đỉnh trụ
    output();   // xuất kết quả ra file
    return (EXIT_SUCCESS);
}

